A Feistel encryption algorithm has a plurality of stirring steps of separating stirred text into two sub-blocks right and left, forming one sub-block to be the sub-block of unstirred text as it is and the other to be stirred, and calculating unstirred text with the other stirred sub-block for encrypting plaintext step by step.
MISTY1, which is this type of Feistel encryption algorithm, includes stirring steps of the Feistel structure formed of an FO function and an FL function being an auxiliary function, having provable security against linear cryptanalysis and differential cryptanalysis, to which eight rounds is recommended for use.
Kuhn shows that traditional MISTY1 with six rounds without the FL function can be attacked by impossible differential attack with 254 of plain text and 261 of complexity. Here, the FL function is a linear function as long as a key is fixed, which does not affect provable security.
Then, the inventor applies traditional higher-order differential cryptanalysis to MISTY1 with six rounds without the FL function, which is the Feistel encryption algorithm, and uses a cryptanalysis method combined with a level-1 first-round elimination to allow MISTY1 with six rounds without the FL function to be encrypted with 239 of selected plaintext and the complexity of 249 of the FO function and to allow MISTY1 with seven rounds without the FL function to be encrypted with 239 of selected plaintext and the complexity of 2124 of the FO function.
Here, the level-1 nth round elimination is a decryption method based on plaintext that stirred text at the nth step satisfies a predetermined condition.